package problems.contest;

import java.util.*;

/**
 * <p>https://leetcode.cn/contest/biweekly-contest-100/</p>
 *
 * @author habitplus
 * @since 2023/3/18 22:28
 */
public class BCT100 {
    /**
     * T1：分类讨论
     */
    public int distMoney(int money, int children) {
        if (money < children) return -1;

        if (money > children * 8) return children - 1;
        else if (money == children * 8) return children;
        else {
            int div = money / 8, mod = money % 8;
            if (children - div == 1 && mod == 4) return div - 1;
            return (money - children) / 7;
        }
    }

    /**
     * T2：贪心 + 排序
     */
    public int maximizeGreatness(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int k = n -1;
        int ret = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[k] > nums[i]) {
                ++ret;
                --k;
            }
        }

        return ret;
    }

    /**
     * T3：模拟 + 排序
     */
    public long findScore(int[] nums) {
        int n = nums.length;
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; ++i) {
            arr[i][0] = i;
            arr[i][1] = nums[i];
        }

        Arrays.sort(arr, (o1, o2) -> o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1]);

        long score = 0;
        for (int i = 0; i < n; ++i) {
            int j = arr[i][0];
            if (nums[j] > -1) {
                // 当前最小值可选
                score += arr[i][1];
                // 标记周围的数
                if (j > 0) nums[j - 1] = -1;
                if (j < n - 1) nums[j + 1] = -1;
            }
        }

        return score;
    }

    /**
     * T4：二分
     */
    public long repairCars(int[] ranks, int cars) {
        long min = Arrays.stream(ranks).min().orElse(0);
        long l = 0, r = min * cars * cars;

        while (l + 1 < r) {
            long m = (l + r) / 2;
            long t = 0;

            for (int g : ranks) {
                t += Math.sqrt(m / g);
            }

            if (t >= cars) r = m;
            else l = m;
        }

        return r;
    }
    public long repairCars1(int[] ranks, int cars) {
        // TME
        int n = ranks.length;
        long spend = 0;
        // 每位工人修车的数量
        int[] rc = new int[n];
        Arrays.fill(rc, 1);
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            long l1 = (long) ranks[o1] * rc[o1] * rc[o1];
            long l2 = (long) ranks[o2] * rc[o2] * rc[o2];
            return (int) (l1 - l2);
        });

        for (int i = 0; i < n; ++i) pq.offer(i);

        for (int k = 1; k <= cars; ++k) {
            // 第 k 辆车交给谁来修
            // 选择划分时间最小的工人
            int j = pq.poll();
            long min = (long) ranks[j] * rc[j] * rc[j];
            spend = Math.max(spend, min);
            // 累加当前工人的修车数量
            ++rc[j];
            pq.offer(j);
        }

        return spend;
    }

}
